package algorithm.color2w.algorithm.array;

import java.util.HashMap;

/**
 * @author wjl <br/>
 * @version 1.0
 * @ClassName: SearchNumIn2DimArray <br/>
 * @Description:
 * 作者：CyC2018
 * 链接：https://www.nowcoder.com/discuss/198840?type=1
 * 来源：牛客网
 *
 * 给定一个二维数组，其每一行从左到右递增排序，从上到下也是递增排序。给定一个数，判断这个数是否在该二维数组中。
 * Consider the following matrix:
 * [
 *   [1,   4,  7, 11, 15],
 *   [2,   5,  8, 12, 19],
 *   [3,   6,  9, 16, 22],
 *   [10, 13, 14, 17, 24],
 *   [18, 21, 23, 26, 30]
 * ]
 *
 * Given target = 5, return true.
 * Given target = 20, return false.
 *
 * 题解：
 * 作者：CyC2018
 * 链接：https://www.nowcoder.com/discuss/198840?type=1
 * 来源：牛客网
 *
 * 要求时间复杂度 O(M + N)，空间复杂度 O(1)。其中 M 为行数，N 为 列数。
 *
 * 该二维数组中的一个数，小于它的数一定在其左边，大于它的数一定在其下边。
 * 因此，从右上角开始查找，就可以根据 target 和当前元素的大小关系来缩小查找区间，当前元素的查找区间为左下角的所有元素。
 * <br />
 * @date: 2019/12/31 16:24<br/>
 */
public class SearchNumIn2DimArray {

    public static void main(String[] args) {
        int arr[][] = new int[][]{
                {1, 4, 7, 11, 15},
                {2, 5, 8, 12, 19},
                {3, 6, 9, 16, 22},
                {10, 13, 14, 17, 24},
                {18, 21, 23, 26, 30}
        };
        System.out.println("-- "+findArrNum(arr,30));
    }

    public static boolean findArrNum(int[][] arr, int param){
        int width = arr[0].length;
        int height = arr.length;
        int zong = 0;
        int heng = width-1;
        while(zong <height && heng >= 0){
            if(param == arr[heng][zong]){
                return true;
            }else if (param < arr[heng][zong]){
                heng--;
            }else {
                zong++;
            }
        }
        return false;
    }
}
